/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

// 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。
// 若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null
// 标记法
var getIntersectionNode = function (headA, headB) {
  while (headA) {
    headA.flag = true
    headA = headA.next
  }
  while (headB) {
    if (headB.flag) return headB
    headB = headB.next
  }
  return null
};

/**
 * 双指针法
 */
var getIntersectionNode = function (headA, headB) {
  var lenA = getLen(headA);
  var lenB = getLen(headB);

  while (lenA > lenB) {
    headA = headA.next;
    lenA--;
  }

  while (lenB > lenA) {
    headB = headB.next;
    lenB--;
  }

  while (headA && headB) {
    if (headA === headB)
      return headA;

    headA = headA.next;
    headB = headB.next;
  }

  return null;
};


function getLen(node) {
  var len = 0;

  while (node) {
    len++;
    node = node.next;
  }

  return len;
}